package com.datastructures.search;

import java.util.Arrays;

/**
 * 斐波那契查找
 * @author MaoLin Wang
 * @date 2019/11/110:45
 */
public class FibonacciSearch {


    public static void main(String[] args) {
        int[] arr = {1, 8, 19, 89, 1000, 1234};

        int i = fibSearch(arr, 1000);
        System.out.println(i);
    }
    public static int maxSize = 20;

    public static int[] fib() {

        int[] f = new int[maxSize];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < maxSize; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f;
    }

    /**
     * 斐波那契查找(非递归方式)
     * @param arr  原数组
     * @param key 目标值
     * @return
     */
    public static int fibSearch(int[] arr,int key){
        int low=0;
        int high=arr.length-1;

        int k=0; //斐波那契分割数值的下标
        int mid= 0;

        int f[]=fib();//获取斐波那契数列


        //获取到斐波那契分割数组的下标
        while (high > f[k] - 1){
            k++;
        }
        //因为f[k]可能大于arr长度，因此需要构造一个新的数组，指向arr[]
        //不足的部分用0补充
        int[] temp= Arrays.copyOf(arr,f[k]);

        //将用0填充的补充使用arr数组最后的数填充
        for (int i=high+1;i<temp.length;i++){
            temp[i]=arr[high];
        }

        //循环查找
        while (low < high){
            mid = low +f[k-1] - 1;
            if (key<temp[mid]){
                //向左查找
                high = mid - 1;

                //f[k] = f[k-1] +f[k-2]
                //可以继续拆分成f[k-1]=f[k-2] +f[k-3],在f[k-1]左边继续查找
                k--;
            }else if (key > temp[mid]){
                //向右查找
                low=mid+1;

                /*
                    说明：
                    1.f[k] = f[k-1] +f[k-2]
                    2.因为后面有f[k-2],所以可以继续拆分f[k-2]=f[k-3] +f[k-4]
                    3.即在f[k-2] 的前面进行查找，K-=2
                    4.即下载循环 mid=f[k-1-2] -1
                 */
                k -=2;
            }else {
                //确定返回的是哪个小标
                if (mid <= high){
                    return mid;
                }else {
                    return high;
                }
            }
        }
        return -1;

    }
}
